package com.kingwood.algorithm.zuochengyun.tanxin1;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/3/23 13:59
 * @Modified By：
 * @Version 1.0
 */
// 最大回文数字
// 给你一个仅由数字（0 - 9）组成的字符串num
// 请你找出能够使用num中数字形成的最大回文整数
// 并以字符串形式返回，该整数不含前导零
// 你无需使用num中的所有数字，但你必须使用至少一个数字，数字可以重新排列
// 测试链接 : https://leetcode.cn/problems/largest-palindromic-number/
public class Code02_LargestPalindromicNumber {
    public static String largestPalindromic(String num) {
        int n = num.length();
        int[] ans = new int[n];
        int[] cnts = new int[10];

        for (char i : num.toCharArray()) {
            cnts[i - '0']++;
        }

        int leftSize = 0;
        int mid = -1;

        for (int i = 9; i >= 1; i--) {
            // 如果是奇数，且mid == -1，那么mid = i
            if ((cnts[i] & 1) == 1 && mid == -1) {
                mid = i;
            }

            for (int j = cnts[i] / 2; j > 0; j--) {
                ans[leftSize++] = i;
            }
        }

        if (leftSize == 0) { // '1'~'9'每一种字符出现次数 <= 1
            if (mid == -1) { // '1'~'9'每一种字符出现次数 == 0
                return "0";
            } else { // '1'~'9'有若干字符出现次数 == 1，其中最大的字符是mid
                return String.valueOf(mid);
            }
        }

        // '1'~'9'有若干字符出现次数 >= 2，左部分已经建立，再考虑把'0'字符填进来
        for (int j = cnts[0] / 2; j > 0; j--) {
            ans[leftSize++] = 0;
        }

        int len = leftSize;
        // 把中点安插进去，中点从来没有被赋值，并且cnt[0]出现了奇数次
        if (mid == -1 && (cnts[0] & 1) == 1) {
            mid = 0;
        }
        if (mid != -1) {
            // 如果有中点加入
            ans[len++] = mid;
        }

        // 左部分逆序拷贝给右部分
        for (int i = leftSize - 1; i >= 0; i--) {
            ans[len++] = ans[i];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            sb.append(ans[i]);
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        char n = '9';
        int mid = n - '0';
        System.out.println(n - 48);
        System.out.println(mid);
        String num = "00011";
        System.out.println(largestPalindromic(num));
    }
}
